package com.kevinkk.stackandqueue;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
 *
 * 用两个栈 一个模拟 入栈 操作，一个模拟 出栈 操作
 * 入栈的话可以一直入栈，出栈时必须保证 出栈 不为空
 *
 * java 中推荐使用 Deque 来实现队列和栈的功能
 */

public class ImplementQueueUsingStacks {
    class MyQueue {
        Deque<Integer> stackIn = new ArrayDeque<>();
        Deque<Integer> stackOut = new ArrayDeque<>();

        public MyQueue() {}

        public void push(int x) {
            stackIn.addFirst(x);

        }

        public int pop() {
            if(stackOut.isEmpty()){
                while(!stackIn.isEmpty())
                    stackOut.addFirst(stackIn.removeFirst());
            }
            return stackOut.removeFirst();
        }

        public int peek() {
            int res = pop();
            stackOut.addFirst(res);
            return res;
        }

        public boolean empty() {
            return stackOut.isEmpty() && stackIn.isEmpty();
        }
    }

}
